Search Results

Documents authored by Duron, Julien

Document
DOI: 10.4230/LIPIcs.IPEC.2023.8
Stretch-Width

Authors: Édouard Bonnet and Julien Duron

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract
We introduce a new parameter, called stretch-width, that we show sits strictly between clique-width and twin-width. Unlike the reduced parameters [BKW '22], planar graphs and polynomial subdivisions do not have bounded stretch-width. This leaves open the possibility of efficient algorithms for a broad fragment of problems within Monadic Second-Order (MSO) logic on graphs of bounded stretch-width. In this direction, we prove that graphs of bounded maximum degree and bounded stretch-width have at most logarithmic treewidth. As a consequence, in classes of bounded stretch-width, Maximum Independent Set can be solved in subexponential time 2^{Õ(n^{8/9})} on n-vertex graphs, and, if further the maximum degree is bounded, Existential Counting Modal Logic [Pilipczuk '11] can be model-checked in polynomial time. We also give a polynomial-time O(OPT²)-approximation for the stretch-width of symmetric 0,1-matrices or ordered graphs. Somewhat unexpectedly, we prove that exponential subdivisions of bounded-degree graphs have bounded stretch-width. This allows to complement the logarithmic upper bound of treewidth with a matching lower bound. We leave as open the existence of an efficient approximation algorithm for the stretch-width of unordered graphs, if the exponential subdivisions of all graphs have bounded stretch-width, and if graphs of bounded stretch-width have logarithmic clique-width (or rank-width).
Cite as

Édouard Bonnet and Julien Duron. Stretch-Width. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.IPEC.2023.8,
  author =	{Bonnet, \'{E}douard and Duron, Julien},
  title =	{{Stretch-Width}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.8},
  URN =		{urn:nbn:de:0030-drops-194279},
  doi =		{10.4230/LIPIcs.IPEC.2023.8},
  annote =	{Keywords: Contraction sequences, twin-width, clique-width, algorithms, algorithmic metatheorems}
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2023.40
PACE Solver Description: RedAlert - Heuristic Track

Authors: Édouard Bonnet and Julien Duron

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract
We present RedAlert, a heuristic solver for twin-width, submitted to the Heuristic Track of the 2023 edition of the Parameterized Algorithms and Computational Experiments (PACE) challenge.
Cite as

Édouard Bonnet and Julien Duron. PACE Solver Description: RedAlert - Heuristic Track. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 40:1-40:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.IPEC.2023.40,
  author =	{Bonnet, \'{E}douard and Duron, Julien},
  title =	{{PACE Solver Description: RedAlert - Heuristic Track}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{40:1--40:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.40},
  URN =		{urn:nbn:de:0030-drops-194591},
  doi =		{10.4230/LIPIcs.IPEC.2023.40},
  annote =	{Keywords: twin-width, contraction sequences, heuristic, pair sampling, pair filtering}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.23
Maximum Independent Set When Excluding an Induced Minor: K₁ + tK₂ and tC₃ ⊎ C₄

Authors: Édouard Bonnet, Julien Duron, Colin Geniet, Stéphan Thomassé, and Alexandra Wesolek

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
Dallard, Milanič, and Štorgel [arXiv '22] ask if, for every class excluding a fixed planar graph H as an induced minor, Maximum Independent Set can be solved in polynomial time, and show that this is indeed the case when H is any planar complete bipartite graph, or the 5-vertex clique minus one edge, or minus two disjoint edges. A positive answer would constitute a far-reaching generalization of the state-of-the-art, when we currently do not know if a polynomial-time algorithm exists when H is the 7-vertex path. Relaxing tractability to the existence of a quasipolynomial-time algorithm, we know substantially more. Indeed, quasipolynomial-time algorithms were recently obtained for the t-vertex cycle, C_t [Gartland et al., STOC '21], and the disjoint union of t triangles, tC₃ [Bonamy et al., SODA '23]. We give, for every integer t, a polynomial-time algorithm running in n^O(t⁵) when H is the friendship graph K₁ + tK₂ (t disjoint edges plus a vertex fully adjacent to them), and a quasipolynomial-time algorithm running in n^{O(t² log n) + f(t)}, with f a single-exponential function, when H is tC₃ ⊎ C₄ (the disjoint union of t triangles and a 4-vertex cycle). The former generalizes the algorithm readily obtained from Alekseev’s structural result on graphs excluding tK₂ as an induced subgraph [Alekseev, DAM '07], while the latter extends Bonamy et al.’s result.
Cite as

Édouard Bonnet, Julien Duron, Colin Geniet, Stéphan Thomassé, and Alexandra Wesolek. Maximum Independent Set When Excluding an Induced Minor: K₁ + tK₂ and tC₃ ⊎ C₄. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.ESA.2023.23,
  author =	{Bonnet, \'{E}douard and Duron, Julien and Geniet, Colin and Thomass\'{e}, St\'{e}phan and Wesolek, Alexandra},
  title =	{{Maximum Independent Set When Excluding an Induced Minor: K₁ + tK₂ and tC₃ ⊎ C₄}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.23},
  URN =		{urn:nbn:de:0030-drops-186769},
  doi =		{10.4230/LIPIcs.ESA.2023.23},
  annote =	{Keywords: Maximum Independent Set, forbidden induced minors, quasipolynomial-time algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact